{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum ASCII Delete Sum for Two Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDeleteSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个字符串的最小ASCII删除和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串<code>s1</code>&nbsp;和&nbsp;<code>s2</code>，返回 <em>使两个字符串相等所需删除字符的&nbsp;<strong>ASCII&nbsp;</strong>值的最小和&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s1 = \"sea\", s2 = \"eat\"\n",
    "<strong>输出:</strong> 231\n",
    "<strong>解释:</strong> 在 \"sea\" 中删除 \"s\" 并将 \"s\" 的值(115)加入总和。\n",
    "在 \"eat\" 中删除 \"t\" 并将 116 加入总和。\n",
    "结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s1 = \"delete\", s2 = \"leet\"\n",
    "<strong>输出:</strong> 403\n",
    "<strong>解释:</strong> 在 \"delete\" 中删除 \"dee\" 字符串变成 \"let\"，\n",
    "将 100[d]+101[e]+101[e] 加入总和。在 \"leet\" 中删除 \"e\" 将 101[e] 加入总和。\n",
    "结束时，两个字符串都等于 \"let\"，结果即为 100+101+101+101 = 403 。\n",
    "如果改为将两个字符串转换为 \"lee\" 或 \"eet\"，我们会得到 433 或 417 的结果，比答案更大。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s1.length, s2.length &lt;= 1000</code></li>\n",
    "\t<li><code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-ascii-delete-sum-for-two-strings](https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-ascii-delete-sum-for-two-strings](https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"sea\"\\n\"eat\"', '\"delete\"\\n\"leet\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        # 使用记忆化搜索实现\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return sum([ord(s) for s in s2[:j + 1]])\n",
    "        #     if j < 0:\n",
    "        #         return sum([ord(s) for s in s1[:i + 1]])\n",
    "        #     if s1[i] == s2[j]:\n",
    "        #         return dfs(i - 1, j - 1)\n",
    "        #     else:\n",
    "        #         return min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))\n",
    "        # return dfs(m - 1, n - 1)\n",
    "\n",
    "        # 使用dp数组实现\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # for i, x in enumerate(s1):\n",
    "        #     # dp[i + 1][0] = sum([ord(s) for s in s1[:i + 1]])\n",
    "        #     dp[i + 1][0] = dp[i][0] + ord(s1[i])\n",
    "        #     for j, y in enumerate(s2):\n",
    "        #         if i == 0:\n",
    "        #             dp[0][j + 1] = dp[0][j] + ord(s2[j])\n",
    "        #         # dp[0][j + 1] = sum([ord(s) for s in s2[:j + 1]])\n",
    "        #         if x == y:\n",
    "        #             dp[i + 1][j + 1] = dp[i][j]\n",
    "        #         else:\n",
    "        #             dp[i + 1][j + 1] = min(dp[i][j + 1] + ord(s1[i]), dp[i + 1][j] + ord(s2[j]))\n",
    "        # return dp[m][n]\n",
    "\n",
    "        # 优化dp数组\n",
    "        # dp = [[0] * (n + 1) for _ in range(2)]\n",
    "        # for i, x in enumerate(s1):\n",
    "        #     dp[(i + 1) % 2][0] = dp[i % 2][0] + ord(s1[i])\n",
    "        #     for j, y in enumerate(s2):\n",
    "        #         if i == 0:\n",
    "        #             dp[0][j + 1] = dp[0][j] + ord(s2[j])\n",
    "        #         if x == y:\n",
    "        #             dp[(i + 1) % 2][j + 1] = dp[i % 2][j]\n",
    "        #         else:\n",
    "        #             dp[(i + 1) % 2][j + 1] = min(dp[i % 2][j + 1] + ord(s1[i]), dp[(i + 1) % 2][j] + ord(s2[j]))\n",
    "        # return dp[m % 2][n]\n",
    "\n",
    "        # 使用一维数组实现\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            dp[i + 1] = dp[i] + ord(s2[i])\n",
    "        for i, x in enumerate(s1):\n",
    "            pre = dp[0]\n",
    "            dp[0] += ord(s1[i])\n",
    "            for j, y in enumerate(s2):\n",
    "                tmp = dp[j + 1]\n",
    "                if x == y:\n",
    "                    dp[j + 1] = pre\n",
    "                else:\n",
    "                    dp[j + 1] = min(dp[j + 1] + ord(s1[i]), dp[j] + ord(s2[j]))\n",
    "                pre = tmp\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        # 使用记忆化搜索实现\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return sum([ord(s) for s in s2[:j + 1]])\n",
    "        #     if j < 0:\n",
    "        #         return sum([ord(s) for s in s1[:i + 1]])\n",
    "        #     if s1[i] == s2[j]:\n",
    "        #         return dfs(i - 1, j - 1)\n",
    "        #     else:\n",
    "        #         return min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))\n",
    "        # return dfs(m - 1, n - 1)\n",
    "\n",
    "        # 使用dp数组实现\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, x in enumerate(s1):\n",
    "            # dp[i + 1][0] = sum([ord(s) for s in s1[:i + 1]])\n",
    "            dp[i + 1][0] = dp[i][0] + ord(s1[i])\n",
    "            for j, y in enumerate(s2):\n",
    "                if i == 0:\n",
    "                    dp[0][j + 1] = dp[0][j] + ord(s2[j])\n",
    "                # dp[0][j + 1] = sum([ord(s) for s in s2[:j + 1]])\n",
    "                if x == y:\n",
    "                    dp[i + 1][j + 1] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = min(dp[i][j + 1] + ord(s1[i]), dp[i + 1][j] + ord(s2[j]))\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        # 使用记忆化搜索实现\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return sum([ord(s) for s in s2[:j + 1]])\n",
    "        #     if j < 0:\n",
    "        #         return sum([ord(s) for s in s1[:i + 1]])\n",
    "        #     if s1[i] == s2[j]:\n",
    "        #         return dfs(i - 1, j - 1)\n",
    "        #     else:\n",
    "        #         return min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))\n",
    "        # return dfs(m - 1, n - 1)\n",
    "\n",
    "        # 使用dp数组实现\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, x in enumerate(s1):\n",
    "            # dp[i + 1][0] = sum([ord(s) for s in s1[:i + 1]])\n",
    "            dp[i + 1][0] = dp[i][0] + ord(s1[i])\n",
    "            for j, y in enumerate(s2):\n",
    "                if i == 0:\n",
    "                    dp[0][j + 1] = dp[0][j] + ord(s2[j])\n",
    "                # dp[0][j + 1] = sum([ord(s) for s in s2[:j + 1]])\n",
    "                if x == y:\n",
    "                    dp[i + 1][j + 1] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = min(dp[i][j + 1] + ord(s1[i]), dp[i + 1][j] + ord(s2[j]))\n",
    "        print(dp)\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        memory = [[-1] * len(s2) for _ in s1]\n",
    "\n",
    "        def dp(s1, s2, i, j):\n",
    "            # base case\n",
    "            if i == len(s1) or j == len(s2):\n",
    "                return 0\n",
    "\n",
    "            if memory[i][j] != -1:\n",
    "                return memory[i][j]\n",
    "\n",
    "            if s1[i] == s2[j]:\n",
    "                memory[i][j] = dp(s1, s2, i + 1, j + 1) + ord(s1[i])\n",
    "            else:\n",
    "                memory[i][j] = max(dp(s1, s2, i + 1, j), dp(s1, s2, i, j + 1))\n",
    "            return memory[i][j]\n",
    "\n",
    "        # 公共部分\n",
    "        communal = dp(s1, s2, 0, 0)\n",
    "\n",
    "        s1Ascii = 0\n",
    "        for i in s1:\n",
    "            s1Ascii += ord(i)\n",
    "        s2Ascii = 0\n",
    "        for j in s2:\n",
    "            s2Ascii += ord(j)\n",
    "\n",
    "        return s1Ascii + s2Ascii - 2 * communal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        def gen_rt(k,t1,pos):\n",
    "            rt = k.copy()\n",
    "            rt[0]+= t1\n",
    "            rt.append(pos)\n",
    "            return rt\n",
    "        def ord_value(s):\n",
    "            return sum(bytearray(s.encode()))\n",
    "\n",
    "        def compare(s1,s2):\n",
    "            s1 = \"a\"+s1\n",
    "            s2 = \"a\"+s2\n",
    "            n1 = len(s1)\n",
    "            n2 = len(s2)\n",
    "            res_same = dict(zip([i for i in range(max(n1,n2))],[-1]*max(n1,n2)))\n",
    "\n",
    "            if n1 > n2:\n",
    "                s1,s2 = s2,s1\n",
    "                n1,n2 = n2,n1\n",
    "            res_ord = {\"a\":97}\n",
    "            res_key = {0:[\"a\",0]}\n",
    "            for i in range(1, n1):\n",
    "                t1 = s1[i]\n",
    "                if t1 not in s2:\n",
    "                    continue\n",
    "                key = ord(t1)\n",
    "                for k in list(res_key.values()):\n",
    "                    pos = s2.find(t1, k[-1] + 1)\n",
    "                    if pos > 0:\n",
    "                        ord_key = res_ord[k[0]]+key\n",
    "                        res_ord[k[0]+t1]=ord_key\n",
    "                        if ord_key > res_same[pos]:\n",
    "                            res_same[pos]=ord_key\n",
    "                            res_key[pos]=gen_rt(k,t1,pos)\n",
    "            maxOrd = 97\n",
    "            for k in res_key.values():\n",
    "                maxOrd = max(maxOrd,ord_value(k[0]))\n",
    "            return ord_value(s1)+ord_value(s2)-2*maxOrd\n",
    "        return compare(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        len1 = len(s1)\n",
    "        len2 = len(s2)\n",
    "\n",
    "        memo = [[0] * (len2 + 1) for _ in range(len1 + 1)]\n",
    "        def dp(s1, start1, s2, start2):\n",
    "            if memo[start1][start2] != 0:\n",
    "                return memo[start1][start2]\n",
    "\n",
    "            if start1 == len1:\n",
    "                memo[start1][start2] = sum(ord(s2[i]) for i in range(start2, len2))\n",
    "                return memo[start1][start2]\n",
    "\n",
    "            if start2 == len2:\n",
    "                memo[start1][start2] = sum(ord(s1[i]) for i in range(start1, len1))\n",
    "                return memo[start1][start2]\n",
    "\n",
    "            if s1[start1] == s2[start2]:\n",
    "                memo[start1][start2] = dp(s1, start1 + 1, s2, start2 + 1)\n",
    "            else:\n",
    "                memo[start1][start2] = min(dp(s1, start1 + 1, s2, start2) + ord(s1[start1]),\n",
    "                                           dp(s1, start1, s2, start2 + 1) + ord(s2[start2]))\n",
    "            return memo[start1][start2]\n",
    "\n",
    "        return dp(s1, 0, s2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        def dp(s1, i, s2, j):\n",
    "            if i >= len(s1) and j >= len(s2):\n",
    "                return 0\n",
    "            if i >= len(s1):\n",
    "                res = 0\n",
    "                for k in range(j, len(s2)):\n",
    "                    res += ord(s2[k])\n",
    "                return res\n",
    "            if j >= len(s2):\n",
    "                res = 0\n",
    "                for k in range(i, len(s1)):\n",
    "                    res += ord(s1[k])\n",
    "                return res\n",
    "            \n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            if s1[i] == s2[j]:\n",
    "                res = dp(s1, i+1, s2, j+1)\n",
    "            else:\n",
    "                delete_all = ord(s1[i]) + ord(s2[j]) + dp(s1, i+1, s2, j+1)\n",
    "                delete_1 = ord(s1[i]) + dp(s1, i+1, s2, j)\n",
    "                delete_2 = ord(s2[j]) + dp(s1, i, s2, j+1)\n",
    "                res = min(delete_all, delete_1, delete_2)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        return dp(s1, 0, s2, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        res = np.zeros((m+1, n+1))\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            res[i, 0] = res[i-1, 0] + ord(s1[i-1])\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            res[0, j] = res[0, j-1] + ord(s2[j-1])\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if s1[i-1] == s2[j-1]:\n",
    "                    res[i, j] = res[i-1, j-1]\n",
    "                else:\n",
    "                    res[i, j] = min(res[i-1, j] + ord(s1[i-1]),\n",
    "                    res[i, j-1] + ord(s2[j-1]))\n",
    "\n",
    "\n",
    "        return int(res[-1][-1]) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self,s1,i,s2,j):\n",
    "        if i==-1:\n",
    "            s=0\n",
    "            for i in s2[:j+1]:\n",
    "                s+=ord(i)\n",
    "            return s\n",
    "        if j==-1:\n",
    "            s=0\n",
    "            for i in s1[:i+1]:\n",
    "                s+=ord(i)\n",
    "            return s\n",
    "        if (i,j) in self.memo:\n",
    "            return self.memo[(i,j)]\n",
    "        if s1[i]==s2[j]:\n",
    "            self.memo[(i,j)]=self.dp(s1,i-1,s2,j-1)\n",
    "        else:\n",
    "            self.memo[(i,j)]=min(self.dp(s1,i-1,s2,j)+ord(s1[i]),self.dp(s1,i,s2,j-1)+ord(s2[j]))\n",
    "        return self.memo[(i,j)]\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m,n=len(s1),len(s2)\n",
    "        self.memo={}\n",
    "        return self.dp(s1,m-1,s2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m, n = len(s1), len(s2)\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        def dp(i, j):\n",
    "            res = 0\n",
    "            if i == m:\n",
    "                for k in range(j, n):\n",
    "                    res += ord(s2[k])\n",
    "                return res\n",
    "            if j == n:\n",
    "                for k in range(i, m):\n",
    "                    res += ord(s1[k])\n",
    "                return res\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            if s1[i] == s2[j]:\n",
    "                memo[i][j] = dp(i + 1, j + 1)\n",
    "            else:\n",
    "                memo[i][j] = min(ord(s1[i]) + dp(i + 1, j), ord(s2[j]) + dp(i, j + 1))\n",
    "            return memo[i][j]\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        def dp(i,j):\n",
    "            sum = 0\n",
    "            if i==rows:# 如果 s1 到头了，那么 s2 剩下的都得删除\n",
    "                for tmp in range(j,cols):\n",
    "                    sum += ord(s2[tmp])\n",
    "                return  sum\n",
    "            if j==cols:# 如果 s2 到头了，那么 s1 剩下的都得删除\n",
    "                for tmp in range(i,rows):\n",
    "                    sum += ord(s1[tmp])\n",
    "                return sum \n",
    "            if memo[i][j]!=-1:\n",
    "                return memo[i][j]\n",
    "            if s1[i] == s2[j]:\n",
    "                memo[i][j] = dp(i+1,j+1)\n",
    "            else:\n",
    "                memo[i][j] = min(ord(s1[i])+dp(i+1,j),ord(s2[j])+dp(i,j+1))\n",
    "            return memo[i][j]\n",
    "        import numpy as np\n",
    "        rows = len(s1) \n",
    "        cols = len(s2)\n",
    "        memo = -np.ones((rows,cols))\n",
    "        return int(dp(0,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        dp = {}\n",
    "        if s1[0] == s2[0]:\n",
    "            dp[(0, 0)] = [ord(s1[0]), s1[0]]\n",
    "        else:\n",
    "            dp[(0, 0)] = [0, \"\"]\n",
    "        \n",
    "        str_ord, sub_str = self.solut(len(s1) - 1, len(s2) - 1, s1, s2, dp)\n",
    "        # print(dp)\n",
    "        return sum([ord(c) for c in s1 + s2]) - 2 * str_ord\n",
    "\n",
    "    def solut(self, i, j, s1, s2, dp):\n",
    "        if (i, j) in dp:\n",
    "            return dp[(i, j)]\n",
    "        \n",
    "        candidates = [0, \"\"]\n",
    "\n",
    "        if s1[i] == s2[j]:\n",
    "            candidates = [ord(s1[i]), s1[i]]\n",
    "       \n",
    "        if i - 1 >= 0 and j - 1 >= 0:\n",
    "            base, sub_str = self.solut(i - 1, j - 1, s1, s2, dp)\n",
    "            candidates[0] += base\n",
    "            candidates[1] = sub_str + candidates[1]\n",
    "\n",
    "        if i - 1 >= 0:\n",
    "            base, sub_str = self.solut(i - 1, j, s1, s2, dp)\n",
    "            if base > candidates[0]:\n",
    "                candidates = [base, sub_str]\n",
    "        \n",
    "        if j - 1 >= 0:\n",
    "            base, sub_str = self.solut(i, j - 1, s1, s2, dp)\n",
    "            if base > candidates[0]:\n",
    "                candidates = [base, sub_str]\n",
    "\n",
    "        dp[(i, j)] = candidates\n",
    "        return dp[(i, j)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/ZhPEchewfc03xWv9VP3msg\n",
    "# 在583题的基础上，知道删除了哪些元素即可\n",
    "\n",
    "# 备忘录方法。memo定义：删除s1[i..]和s2[j..]中，那个啥啥的最小ascii码之和\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m, n = len(s1), len(s2)\n",
    "        # 备忘录值为 -1 代表未曾计算\n",
    "        memo = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            res = 0\n",
    "            # base case\n",
    "            if i == m:\n",
    "                # 如果 s1 到头了，那么 s2 剩下的都得删除\n",
    "                for k in range(j, n):\n",
    "                    res += ord(s2[k])\n",
    "                return res\n",
    "            if j == n:\n",
    "                # 如果 s2 到头了，那么 s1 剩下的都得删除\n",
    "                for k in range(i, m):\n",
    "                    res += ord(s1[k])\n",
    "                return res\n",
    "\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            if s1[i] == s2[j]:\n",
    "                # s1[i] 和 s2[j] 都是在 lcs 中的，不用删除\n",
    "                memo[i][j] = dp(i + 1, j + 1)\n",
    "            else:\n",
    "                # s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个\n",
    "                memo[i][j] = min(\n",
    "                    ord(s1[i]) + dp(i+1, j),\n",
    "                    ord(s2[j]) + dp(i, j+1)\n",
    "            )\n",
    "\n",
    "            return memo[i][j]\n",
    "\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        l1,l2 = len(s1),len(s2)\n",
    "        memo = [[-1 for _ in range(l2)] for _ in range(l1)]\n",
    "\n",
    "        def dp(s1,m,s2,n):\n",
    "            nonlocal memo\n",
    "            rtn = 0\n",
    "            if m == -1:\n",
    "                for i in range(n+1):\n",
    "                    rtn += ord(s2[i])\n",
    "                return rtn\n",
    "            if n == -1:\n",
    "                for j in range(m+1):\n",
    "                    rtn += ord(s1[j])\n",
    "                return rtn\n",
    "            if memo[m][n] != -1:\n",
    "                return memo[m][n]\n",
    "\n",
    "            if s1[m] == s2[n]:\n",
    "                memo[m][n] = dp(s1,m-1,s2,n-1)\n",
    "            else:\n",
    "                memo[m][n] = min(dp(s1,m-1,s2,n)+ord(s1[m]),dp(s1,m,s2,n-1)+ord(s2[n]),\n",
    "                           dp(s1,m-1,s2,n-1)+ord(s1[m])+ord(s2[n]))\n",
    "            return memo[m][n]\n",
    "        return dp(s1,l1-1,s2,l2-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        memo = [[-1] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # 定义dp函数为s1[i...]和s2[j...]相等所需删除字符的 ASCII 值的最小和 \n",
    "        def dp(i, j):\n",
    "            res = 0\n",
    "            # 如果s1遍历完，s2剩余字符全部删除\n",
    "            if i == m:\n",
    "                while j < n:\n",
    "                    res += ord(s2[j])\n",
    "                    j += 1\n",
    "                return res\n",
    "            # 如果s2遍历完，s1剩余字符全部删除\n",
    "            if j == n:\n",
    "                while i < m:\n",
    "                    res += ord(s1[i])\n",
    "                    i += 1\n",
    "                return res\n",
    "            \n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            if s1[i] == s2[j]:\n",
    "                res += dp(i + 1, j + 1)\n",
    "                \n",
    "            else:\n",
    "                res += min(ord(s1[i]) + dp(i+1, j), ord(s2[j]) + dp(i, j + 1))\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        return dp(0 ,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        heap = [(0, s1, s2)]\n",
    "        visited = set()\n",
    "        while heap:\n",
    "            _sum, w1, w2 = heappop(heap)\n",
    "            if w1 == w2:\n",
    "                return _sum\n",
    "            if (w1, w2) in visited:\n",
    "                continue\n",
    "            visited.add((w1, w2))\n",
    "            if w1 and w2 and w1[0] == w2[0]:\n",
    "                heappush(heap, (_sum, w1[1:], w2[1:]))\n",
    "            else:\n",
    "                if w1:\n",
    "                    heappush(heap, (_sum + ord(w1[0]), w1[1:], w2))\n",
    "                if w2:\n",
    "                    heappush(heap, (_sum + ord(w2[0]), w1, w2[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cals = [[-1 for i in range(len(s2))] for j in range(len(s1))]\n",
    "        def dynamic(i, j):\n",
    "            ans = 0\n",
    "            if i >= len(s1):\n",
    "                for m in s2[j:]:\n",
    "                    ans += ord(m)\n",
    "                return ans\n",
    "            if j >= len(s2):\n",
    "                for m in s1[i:]:\n",
    "                    ans += ord(m)\n",
    "                return ans\n",
    "            if cals[i][j] > 0:\n",
    "                return cals[i][j]\n",
    "            if s1[i] == s2[j]:\n",
    "                cals[i][j] = dynamic(i+1, j+1)\n",
    "            else:\n",
    "                cals[i][j] = min([dynamic(i+1, j) + ord(s1[i]), dynamic(i, j+1) + ord(s2[j]), dynamic(i+1, j+1) + ord(s1[i]) + ord(s2[j])])\n",
    "            return cals[i][j]\n",
    "        return dynamic(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        text1 = s1\n",
    "        text2 = s2\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(i, j):\n",
    "            if i == m or j == n:\n",
    "                return 0\n",
    "            t = text1[i]\n",
    "            try:\n",
    "                idx = text2.index(t, j)\n",
    "                return max(ord(t) + f(i + 1, idx + 1), f(i + 1, j))\n",
    "            except ValueError:\n",
    "                return f(i + 1, j)\n",
    "        c = f(0, 0)\n",
    "        return sum(ord(c) for c in s1) - c + sum(ord(c) for c in s2) - c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ret = {}\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        if self.ret.get((s1, s2), 0):\n",
    "            return self.ret[(s1, s2)]\n",
    "        if not s1 and not s2:\n",
    "            return 0\n",
    "        if not s1:\n",
    "            return sum(ord(i) for i in s2)\n",
    "        elif not s2:\n",
    "            return sum(ord(i) for i in s1)\n",
    "        if s1[0] == s2[0]:\n",
    "            a = self.minimumDeleteSum(s1[1:], s2[1:])\n",
    "            b = a\n",
    "        else:\n",
    "            a = self.minimumDeleteSum(s1[1:], s2) + ord(s1[0])\n",
    "            b = self.minimumDeleteSum(s1, s2[1:]) + ord(s2[0])\n",
    "        self.ret[(s1, s2)] = min(a, b)\n",
    "        return self.ret[(s1, s2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    # maxsize 是指定最大缓存多少个调用，默认为 128，如果设置为 None 则关闭缓存功能\n",
    "    # typed 是指定参数值相同但类型不同时是否单独缓存，默认值为 False\n",
    "    @lru_cache(maxsize=100000, typed=False)\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        if len(s1) == 0:\n",
    "            s = 0\n",
    "            for i in s2:\n",
    "                s += ord(i)\n",
    "            return s\n",
    "        elif len(s2) == 0:\n",
    "            s = 0\n",
    "            for i in s1:\n",
    "                s += ord(i)\n",
    "            return s\n",
    "        else:\n",
    "            if s1[0] != s2[0]:\n",
    "                return min(ord(s1[0]) + self.minimumDeleteSum(s1[1:], s2), ord(s2[0]) + self.minimumDeleteSum(s1, s2[1:]))\n",
    "            else:\n",
    "                return self.minimumDeleteSum(s1[1:], s2[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s: str, t: str) -> int:\n",
    "        memo = {}\n",
    "        def helper(s, t):\n",
    "            k = (s, t)\n",
    "            if k not in memo:\n",
    "                if not s or not t:\n",
    "                    r = 0\n",
    "                    for c in s + t:\n",
    "                        r += ord(c)\n",
    "                    memo[k] = r\n",
    "                elif s[0] == t[0]:\n",
    "                    memo[k] = helper(s[1:], t[1:])\n",
    "                else:\n",
    "                    memo[k] = min(\n",
    "                        ord(s[0]) + helper(s[1:], t),\n",
    "                        ord(t[0]) + helper(s, t[1:])\n",
    "                    )\n",
    "            return memo[k]\n",
    "        return helper(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 用脚指头想想都能知道这题又和最长公共子序列有关\n",
    "        # 方法一：dp\n",
    "        # time complexity: O(n^2), space complexity: O(n^2)\n",
    "        m, n = len(s1), len(s2)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        # edge case\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = dp[0][j-1] + ord(s2[j-1])\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = dp[i-1][0] + ord(s1[i-1])\n",
    "        # dp\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if s1[i-1] == s2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1]))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        memory = {}\n",
    "        def dp(i, j):\n",
    "            if i == -1:\n",
    "                return sum([ord(c) for c in s2[:j + 1]])\n",
    "            if j == -1:\n",
    "                return sum([ord(c) for c in s1[:i + 1]])\n",
    "            key = \"{}-{}\".format(i, j)\n",
    "            if key in memory:\n",
    "                return memory[key]\n",
    "            if s1[i] == s2[j]:\n",
    "                cur = dp(i - 1, j - 1)\n",
    "            else:\n",
    "                cur = min(\n",
    "                        dp(i - 1, j) + ord(s1[i]), # i 左移，代表删除s1[i]\n",
    "                        dp(i, j - 1) + ord(s2[j]), # j 左移，代表删除s2[j]\n",
    "                        )\n",
    "            memory[key] = cur \n",
    "            return cur \n",
    "        return dp(len(s1) - 1, len(s2) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def fun(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            res=0\n",
    "            if i == 0 and j >= 0:\n",
    "\n",
    "                return 0\n",
    "\n",
    "            if j == 0 and i >= 0:\n",
    "\n",
    "                return 0\n",
    "            if s1[i - 1] == s2[j - 1]:\n",
    "\n",
    "                memo[(i, j)] = fun(i - 1, j - 1) + ord(s1[i - 1])\n",
    "            else:\n",
    "\n",
    "                memo[(i, j)] = max(fun(i - 1, j), fun(i, j - 1))\n",
    "            return memo[(i, j)]\n",
    "\n",
    "        return sum(map(ord,s1+s2))-2*fun(len(s1), len(s2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        \n",
    "        self.memo = {}\n",
    "        self.len1, self.len2 = len(s1), len(s2)\n",
    "        def lcs(s1, s2, i, j):\n",
    "            if i == self.len1 or j == self.len2:\n",
    "                return 0\n",
    "            if (i, j) in self.memo:\n",
    "                return self.memo[(i, j)]\n",
    "            if s1[i] == s2[j]:\n",
    "                lcs_ord = ord(s1[i]) + lcs(s1, s2, i+1, j+1)\n",
    "            else:\n",
    "                lcs_ord = max(lcs(s1, s2, i+1, j), lcs(s1, s2, i, j+1))\n",
    "            self.memo[(i, j)] = lcs_ord\n",
    "            return lcs_ord\n",
    "        ascii1 = sum([ord(s) for s in s1])\n",
    "        ascii2 = sum([ord(s) for s in s2])\n",
    "        ascii_common = lcs(s1, s2, 0, 0)\n",
    "        return ascii1 + ascii2 - 2*ascii_common"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m, n = len(s1), len(s2)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            \n",
    "            if s1[i] == s2[j]:\n",
    "                return dfs(i-1, j-1) + ord(s1[i])\n",
    "            return max(dfs(i-1, j), dfs(i, j-1))\n",
    "\n",
    "        ans = dfs(m-1, n-1)\n",
    "\n",
    "        ord1 = ord2 = 0\n",
    "        for c in s1:\n",
    "            ord1 += ord(c)\n",
    "        for c in s2:\n",
    "            ord2 += ord(c)\n",
    "        \n",
    "        return ord1-ans+ord2-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        memo = defaultdict(int)\n",
    "        # dp[i][j] => s1[0...i] s2[0...j]\n",
    "        # dp[i][j] => s1[i...] s2[j...]\n",
    "        def dp(i: int, j: int) -> int: \n",
    "            key = \"{}_{}\".format(i, j)\n",
    "            if i == len(s1):\n",
    "                ans = 0\n",
    "                for k in range(j, len(s2)):\n",
    "                    ans += ord(s2[k])\n",
    "                return ans\n",
    "                \n",
    "            if j == len(s2):\n",
    "                ans = 0\n",
    "                for k in range(i, len(s1)):\n",
    "                    ans += ord(s1[k])\n",
    "                return ans\n",
    "\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            if s1[i] == s2[j]:\n",
    "                memo[key] = dp(i+1, j+1)\n",
    "            else:\n",
    "                memo[key] = min(dp(i+1, j) + ord(s1[i]), dp(i, j+1) + ord(s2[j]))\n",
    "            return memo[key]\n",
    "        return dp(0, 0)\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        # maximize LCS ascii value\n",
    "        # f[i][j] = f[i-1][j-1]+s1[i] if s1[i] == s2[j]\n",
    "        #         = max(f[i][j-1], f[i-1][j])\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == -1 or j == -1: return 0\n",
    "            if s1[i] == s2[j]: return f(i-1, j-1)+ord(s1[i])\n",
    "            else: return max(f(i, j-1), f(i-1, j))\n",
    "        return sum(ord(x) for x in s1+s2)-2*f(len(s1)-1, len(s2)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            if i<0 or j<0:\n",
    "                return 0\n",
    "            if s1[i]!=s2[j]:\n",
    "                return max(dp(i-1,j),dp(i,j-1))\n",
    "            return dp(i-1,j-1)+ord(s1[i])\n",
    "        add=0\n",
    "        for ch in s1:\n",
    "            add+=ord(ch)\n",
    "        for ch in s2:\n",
    "            add+=ord(ch)\n",
    "        return add-2*dp(len(s1)-1,len(s2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "\n",
    "        ps1 = [0 for _ in range(n1)]\n",
    "        for i in range(n1):\n",
    "            if i == 0:\n",
    "                ps1[i] = ord(s1[i])\n",
    "            else:\n",
    "                ps1[i] += ord(s1[i]) + ps1[i-1]\n",
    "\n",
    "        ps2 = [0 for _ in range(n2)]\n",
    "        for i in range(n2):\n",
    "            ps2[i] = ord(s2[i]) + (0 if i == 0 else ps2[i-1])\n",
    "\n",
    "        @cache\n",
    "        def process(i, j):\n",
    "            if i == -1 and j == -1:\n",
    "                return 0\n",
    "            if i == -1:\n",
    "                return ps2[j]\n",
    "            if j == -1:\n",
    "                return ps1[i]\n",
    "\n",
    "            v1 = ord(s1[i]) + process(i-1, j)\n",
    "\n",
    "            for k in range(j, -1, -1):\n",
    "                if s2[k] == s1[i]:\n",
    "                    break\n",
    "            else:\n",
    "                return v1\n",
    "            \n",
    "            v2 = ps2[j] - ps2[k]\n",
    "            v2 += process(i-1, k-1)\n",
    "            return min(v1, v2)\n",
    "        \n",
    "        return process(n1-1, n2-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        # 要使删除字符的ASCII码的值的和最小，那么就要使字符串相等的和最大\n",
    "        res = sum(ord(a) for a in s1 + s2)\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= n or j >= m:\n",
    "                return 0\n",
    "        #情况一 如果 s1[i] != s2[j]\n",
    "        #那么就有两种选择，寻找LCS(s1[i+1:],s2[j:])或LCS(s1[i:],s2[j+1])两者之间的最大权值\n",
    "            tmp = max(dfs(i+1,j),dfs(i,j+1))\n",
    "            if s1[i] == s2[j]:\n",
    "        # 情况二 如果 s1[i] == s2[j],那么在情况一的基础上做出选择，把ASCII码加上即可\n",
    "                tmp = max(tmp,dfs(i+1,j+1) + ord(s1[i]))\n",
    "            return tmp\n",
    "        return res - 2 * dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\r\n",
    "        '''\r\n",
    "        stat: remaining two strings\r\n",
    "        choices: 1) delete s1, 2) delete s2, 3) not delete\r\n",
    "        '''\r\n",
    "        def dp(s1, s2, i, j):\r\n",
    "            res = 0\r\n",
    "            if i >= len(s1):\r\n",
    "                for ch in s2[j:]:\r\n",
    "                    res += ord(ch)\r\n",
    "                return res\r\n",
    "            if j >= len(s2):\r\n",
    "                for ch in s1[i:]:\r\n",
    "                    res += ord(ch)\r\n",
    "                return res\r\n",
    "\r\n",
    "            key = (i, j)\r\n",
    "            if key in memo:\r\n",
    "                return memo[key]\r\n",
    "\r\n",
    "            if s1[i] == s2[j]:\r\n",
    "                return dp(s1, s2, i+1, j+1)\r\n",
    "            \r\n",
    "            del_1 = dp(s1, s2, i+1, j) + ord(s1[i])\r\n",
    "            del_2 = dp(s1, s2, i, j+1) + ord(s2[j])\r\n",
    "            # print(i+1, j, del_1)\r\n",
    "            # print(i, j+1, del_2)\r\n",
    "            # print()\r\n",
    "            min_asic = min(del_1, del_2)\r\n",
    "            memo[key] = min_asic\r\n",
    "            return min_asic\r\n",
    "        \r\n",
    "        memo = dict()\r\n",
    "        return dp(s1, s2, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        def dp(i, j):\n",
    "            nonlocal memo\n",
    "            if i < 0:\n",
    "                tmp = 0\n",
    "                for s in s2[:j+1]:\n",
    "                    tmp += ord(s)\n",
    "                return tmp\n",
    "            if j < 0:\n",
    "                tmp = 0\n",
    "                for s in s1[:i+1]:\n",
    "                    tmp += ord(s)\n",
    "                return tmp\n",
    "            if (i ,j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if s1[i] == s2[j]:\n",
    "                return dp(i-1, j-1)\n",
    "            memo[(i, j)] = min(dp(i-1, j)+ord(s1[i]), dp(i, j-1)+ord(s2[j]))\n",
    "            return memo[(i, j)]\n",
    "        memo = dict()\n",
    "        return dp(len(s1)-1, len(s2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        dic = dict()\n",
    "        m, n = len(s1), len(s2)\n",
    "        def dp(i, j):\n",
    "            res = 0\n",
    "            if i == m:\n",
    "                for k in range(j, n):\n",
    "                    res += ord(s2[k])\n",
    "                return res\n",
    "            elif j == n:\n",
    "                for k in range(i, m):\n",
    "                    res += ord(s1[k])\n",
    "                return res\n",
    "            else:\n",
    "                if (i,j) in dic:\n",
    "                    return dic[(i,j)]\n",
    "                if s1[i] == s2[j]:\n",
    "                    dic[(i,j)] = dp(i+1, j+1)\n",
    "                else:\n",
    "                    dic[(i,j)] = min(dp(i, j+1)+ord(s2[j]), dp(i+1,j)+ord(s1[i]))\n",
    "                return dic[(i,j)]\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m, n = len(s1), len(s2)\n",
    "        memo = {}\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i == m and j == n :\n",
    "                return 0\n",
    "            if i == m:\n",
    "                return sum(ord(x) for x in s2[j:])\n",
    "            if j == n:\n",
    "                return sum(ord(x) for x in s1[i:])\n",
    "            res = float('inf')\n",
    "            if s1[i] == s2[j]:\n",
    "                res = dfs(i+1, j+1)\n",
    "            else:\n",
    "                res = min(dfs(i+1, j) + ord(s1[i]), dfs(i, j+1) + ord(s2[j]))\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        # ascii 最小和\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return sum(ord(s2[idx]) for idx in range(j+1))\n",
    "            if j < 0:\n",
    "                return sum(ord(s1[idx]) for idx in range(i+1))\n",
    "            \n",
    "            if s1[i] == s2[j]:\n",
    "                return dfs(i-1, j-1)\n",
    "            \n",
    "            return min(dfs(i-1, j) + ord(s1[i]), dfs(i, j-1) + ord(s2[j]))\n",
    "        \n",
    "        return dfs(n-1, m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        @cache\n",
    "        def getSum(type, i):\n",
    "            sum = 0\n",
    "            if type == 1:\n",
    "                for i in range(i + 1):\n",
    "                    sum += ord(s1[i])\n",
    "            else:\n",
    "                for i in range(i + 1):\n",
    "                    sum += ord(s2[i])\n",
    "            return sum\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if (i < 0): return getSum(2, j)\n",
    "            if (j < 0): return getSum(1, i)\n",
    "            if s1[i] == s2[j]: return dfs(i - 1, j - 1)\n",
    "            return min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))\n",
    "\n",
    "        return dfs(len(s1) - 1, len(s2) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        memo={}\n",
    "        def dp(i,j):\n",
    "            if i==-1:\n",
    "                return sum([ ord(i) for i in s2[0:j+1]])\n",
    "            if j==-1:\n",
    "                return sum([ ord(i) for i in s1[0:i+1]])\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if s1[i]==s2[j]:\n",
    "                memo[(i,j)]=dp(i-1,j-1)\n",
    "                return memo[(i,j)]\n",
    "            else:\n",
    "                memo[(i,j)]=min(dp(i,j-1)+ord(s2[j]) ,dp(i-1,j)+ord(s1[i])  )\n",
    "\n",
    "                return memo[(i,j)]\n",
    "        return dp(len(s1)-1,len(s2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        cnt1 = sum([ord(a) for a in s1]+[ord(a) for a in s2])\n",
    "        s1 = ''.join([c for c in s1 if c in s2])\n",
    "        s2 = ''.join([c for c in s2 if c in s1])\n",
    "        ans = sum([ord(a) for a in s1]+[ord(a) for a in s2])\n",
    "        diff = cnt1-ans\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i == j == -1:return 0\n",
    "            if i == -1: return sum([ord(a) for a in s2[:j+1]])\n",
    "            if j == -1: return sum([ord(a) for a in s1[:i+1]])\n",
    "\n",
    "            if s1[i]==s2[j]: return dp(i-1, j-1)\n",
    "            return min(dp(i-1, j)+ord(s1[i]) , dp(i, j-1)+ord(s2[j]))\n",
    "        return dp(len(s1)-1, len(s2)-1)+diff\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeleteSum(self, s1: str, s2: str) -> int:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        # 使用记忆化搜索实现\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return sum([ord(l) for l in s2[:j + 1]])\n",
    "            if j < 0:\n",
    "                return sum([ord(l) for l in s1[:i + 1]])\n",
    "            if s1[i] == s2[j]:\n",
    "                return dfs(i - 1, j - 1)\n",
    "            else:\n",
    "                return min(dfs(i, j - 1) + ord(s2[j]), dfs(i - 1, j) + ord(s1[i]))\n",
    "        return dfs(m - 1, n - 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
